Most profit assigning work

Time: O(MLogM+NLogN); Space: O(N); medium

We have jobs:

  • difficulty[i] is the difficulty of the ith job, and

  • profit[i] is the profit of the ith job.

Now we have some workers. worker[i] is the ability of the ith worker, which means that this worker can only complete a job with difficulty at most worker[i].

Every worker can be assigned at most one job, but one job can be completed multiple times.

For example, if 3 people attempt the same job that pays $1, then the total profit will be $3. If a worker cannot complete any job, his profit is $0.

What is the most profit we can make?

Example 1:

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]

Output: 100

Explanation:

  • Workers are assigned jobs of difficulty [4,4,6,6] and they get profit of [20,20,30,30] seperately.

Constraints:

  • 1 <= len(difficulty) = len(profit) <= 10000

  • 1 <= len(worker) <= 10000

  • difficulty[i], profit[i], worker[i] are in range [1, 10^5]

1. Sorting Events [O(MLogM+NLogN),O(N)]

Intuition

We can consider the workers in any order, so let’s process them in order of skill.

If we processed all jobs with lower skill first, then the profit is just the most profitable job we have seen so far.

Algorithm

We can use a “two pointer” approach to process jobs in order. We will keep track of best, the maximum profit seen.

For each worker with a certain skill, after processing all jobs with lower or equal difficulty, we add best to our answer.

[6]:

class Solution1(object):
    """
    Time: O(MLogM+NLogN), N is the number of jobs, M is the number of workers,
    Space: O(N)
    """
    def maxProfitAssignment(self, difficulty, profit, worker):
        """
        :type difficulty: List[int]
        :type profit: List[int]
        :type worker: List[int]
        :rtype: int
        """
        jobs = list(zip(difficulty, profit))

        jobs.sort()
        worker.sort()

        result, i, max_profit = 0, 0, 0

        for ability in worker:
            while i < len(jobs) and jobs[i][0] <= ability:
                max_profit = max(max_profit, jobs[i][1])
                i += 1
            result += max_profit

        return result

[7]:

s = Solution1()
difficulty = [2,4,6,8,10]
profit = [10,20,30,40,50]
worker = [4,5,6,7]
assert s.maxProfitAssignment(difficulty, profit, worker) == 100